#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//https://leetcode.cn/problems/shortest-string-that-contains-three-strings/description/
//包含三个字符串的最短字符串
//给你三个字符串 a ，b 和 c ， 你的任务是找到长度 最短 的字符串，且这三个字符串都是它的 子字符串 。
//如果有多个这样的字符串，请你返回 字典序最小 的一个。
//请你返回满足题目要求的字符串。
//注意：
//两个长度相同的字符串 a 和 b ，如果在第一个不相同的字符处，a 的字母在字母表中比 b 的字母 靠前 ，那么字符串 a 比字符串 b 字典序小 。
//子字符串 是一个字符串中一段连续的字符序列。

char* LinkString(char* str1, char* str2)
{
    if(str1 == NULL||strstr(str2, str1) != NULL)
    return str2;
    if(str2 == NULL||strstr(str1, str2) != NULL)
    return str1;

    int common = 0;
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    for(int i = 0; i < len1; i++)
    {
        if(strncmp(str1 + i, str2, len1 - i) == 0)
        {
            common = len1 - i;
            break;
        }
    }
    int len = len1 + len2 - common;
    char* str = (char*)malloc(sizeof(char) * (len + 1));
    strcpy(str, str1);
    for(int i = 0; i < len2 - common; i++)
    {
        str[i + len1] = str2[common + i];
    }
    str[len] = '\0';
    return str;
}

int cmp(const void* str1, const void* str2)
{
    char* a = *(char**)str1;
    char* b = *(char**)str2;
    int len1 = strlen(a);
    int len2 = strlen(b);
    if(len1 != len2)
    {
        return len1 - len2;
    }
    else
    {
        return strcmp(a, b);
    }
}

char * minimumString(char * a, char * b, char * c){
    int len = strlen(a) + strlen(b) + strlen(c);
    char** allret = (char**)malloc(sizeof(char*) * 6);
    for(int i = 0; i < 6; i++)
    {
        allret[i] = (char*)malloc(sizeof(char) * (len + 1));
    }

    char* ab = LinkString(a, b);
    char* ba = LinkString(b, a);
    char* ac = LinkString(a, c);
    char* ca = LinkString(c, a);
    allret[0] = LinkString(ab, c);
    allret[1] = LinkString(ac, b);
    allret[2] = LinkString(ba, c);
    allret[3] = LinkString(b, ca);//
    allret[4] = LinkString(c, ab);//
    allret[5] = LinkString(c, ba);

    qsort(allret, 6, sizeof(char*), cmp);
    return allret[0];
}

int main()
{
    char* a = "bab";
    char* b = "a";
    char* c = "b";
    printf("%s\n", minimumString(a, b, c));
    return 0;
}